package com.arron.algorithm.leetcodetop100.回溯.排列and组合and子集;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *  90. 子集II
 */
public class 子集II {

    List<List<Integer>> allSubList;

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        List<Integer> subList = new ArrayList<>();
        allSubList = new ArrayList<>();
        Arrays.sort(nums);
        subsets(nums,subList,0);
        return allSubList;
    }

    public void subsets(int[] nums,List<Integer> subList,int start){

        allSubList.add(new ArrayList<>(subList));

        for (int i = start; i < nums.length; i++) {
            //剪枝，去除重复
            if (i>start && nums[i] == nums[i-1]){
                continue;
            }
            subList.add(nums[i]);
            subsets(nums,subList,i+1);
            subList.remove(subList.size()-1);
        }

    }
}
